public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.addBinary("10", "101"));
    }

    public String addBinary1(String a, String b) {
        /**
         * 二进制求和
         *  解法一：使用无进位相加解决，将字符串当成位运算*/
        // 1 预处理（补全字符串，使得两者长度一致）
        int l1 = a.length();
        int l2 = b.length();
        if(l1 < l2) {
            String front = "";
            for(int i = l1; i < l2; i++) {
                front += "0";
            }
            a = front + a;
        } else {
            String front = "";
            for(int i = l2; i < l1; i++) {
                front += "0";
            }
            b = front + b;
        }

        // 2 无进位相加求和
        while(true) {
            // -1 异或求得无进位相加
            String noUp = "";
            for(int i = 0; i < a.length(); i++) {
                if(a.charAt(i) == b.charAt(i)) {
                    noUp += "0";
                } else {
                    noUp += "1";
                }
            }

            // -2 按位与求得进位信息（此处决定是否退出循环）
            boolean flg = true;
            String upInfo = "";
            for(int i = 0; i < a.length(); i++) {
                if(a.charAt(i) == b.charAt(i) && b.charAt(i) == '1') {
                    upInfo += "1";
                    flg = false;
                } else {
                    upInfo += "0";
                }
            }
            if(flg) {
                a = noUp;
                break;
            }

            // -3 循环赋值计算进位
            upInfo = upInfo + "0";
            a = noUp;
            b = upInfo.substring(1);
            if(upInfo.charAt(0) == '1') {
                a = "0" + a;
                b = "1" + b;
            }
        }

        // 3 去除多余前置0
        int i = 0;
        while(i < a.length() && a.charAt(i) == '0') {
            i ++;
        }
        if(i == a.length()) {
            return "0";
        } else {
            return a.substring(i);
        }
    }

    public String addBinary(String a, String b) {
        /**
         * 二进制求和
         *  解法二：高精度加法：模拟列竖式相加*/
        // 1 预处理（补全字符串，使得两者长度一致）
        int l1 = a.length();
        int l2 = b.length();
        if(l1 < l2) {
            String front = "";
            for(int i = l1; i < l2; i++) {
                front += "0";
            }
            a = front + a;
        } else {
            String front = "";
            for(int i = l2; i < l1; i++) {
                front += "0";
            }
            b = front + b;
        }

        // 2 模拟
        int temp = 0;
        String ret = "";
        for(int i = a.length()-1; i >= 0; i--) {
            int cur = a.charAt(i) - '0' + b.charAt(i) - '0' + temp;
            ret = cur%2 + ret;
            temp = cur/2;
        }
        if(temp == 1) {
            ret = "1" + ret;
        }

        // 3 返回值
        // 3 去除多余前置0
        int i = 0;
        while(i < ret.length() && ret.charAt(i) == '0') {
            i ++;
        }
        if(i == ret.length()) {
            return "0";
        } else {
            return ret;
        }
    }


}
